// 删除链表的倒数第 N 个结点
class Solution {
    public:
        ListNode* removeNthFromEnd(ListNode* head, int n) {
            ListNode *newhead = new ListNode(0, head);
            ListNode *l = newhead, *r = head;
            while (n--) r = r->next;
            while (r)
            {
                r = r->next;
                l = l->next;
            }
            l->next = l->next->next;
            head = newhead->next;
            return head;
        }
    };

// 两数相加
class Solution {
    public:
        ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
            int t = 0;
            ListNode* newhead = new ListNode();
            ListNode* tail = newhead;
            while (l1 || l2)
            {
                if (l1)
                {
                    t += l1->val;
                    l1 = l1->next;
                }
                if (l2)
                {
                    t += l2->val;
                    l2 = l2->next;
                }
                tail->next = new ListNode(t % 10);
                t /= 10;
                tail = tail->next;
            }
            if (t) tail->next = new ListNode(t);
            tail = newhead->next;
            delete newhead;
            return tail;
        }
    };

// 回文链表
class Solution {
    public:
        bool isPalindrome(ListNode* head) {
            ListNode* fast = head, *slow = head;
            while (fast && fast->next)
            {
                slow = slow->next;
                fast = fast->next->next;
            }
            // 翻转后半部分
            ListNode* prev = nullptr;
            while (slow)
            {
                ListNode* next = slow->next;
                slow->next = prev;
                prev = slow;
                slow = next;
            }
            // 比较是否回文
            ListNode* cur1 = head, *cur2 = prev;
            while (cur1 && cur2 && cur1->val == cur2->val)
            {
                cur1 = cur1->next;
                cur2 = cur2->next;
            }
            return cur2 == nullptr;
        }
    };